Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

Solution:

  1. public class Solution {
  2.   public List<String> findMissingRanges(int[] a, int lo, int hi) {
  3.     List<String> res = new ArrayList<String>();
  5.     // the next number we need to find
  6.     int next = lo;
  8.     for (int i = 0; i < a.length; i++) {
  9.       // not within the range yet
  10.       if (a[i] < next) continue;
  12.       // continue to find the next one
  13.       if (a[i] == next) {
  14.         next++;
  15.         continue;
  16.       }
  18.       // get the missing range string format
  19.       res.add(getRange(next, a[i] - 1));
  21.       // now we need to find the next number
  22.       next = a[i] + 1;
  23.     }
  25.     // do a final check
  26.     if (next <= hi) res.add(getRange(next, hi));
  28.     return res;
  29.   }
  31.   String getRange(int n1, int n2) {
  32.     return (n1 == n2) ? String.valueOf(n1) : String.format("%d->%d", n1, n2);
  33.   }
  34. }